public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
    public int minCostClimbingStairs(int[] cost) {
      int n = cost.length;
      int[] dp = new int[n];
      dp[n-1]=cost[n-1];
      dp[n-2]=cost[n-2];
      for(int i=n-3;i>=0;i--){
          dp[i]=Math.min(dp[i+1],dp[i+2])+cost[i];
      }
      return Math.min(dp[0],dp[1]);
    }
    public int minCostClimbingStairs2(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];
        dp[0]=0;
        dp[1]=0;
        for(int i=2; i<=n; i++){
            dp[i]=Math.min(dp[i-2]+cost[i-2], dp[i-1]+cost[i-1]);
        }
        return dp[n];
    }
    public int numDecodings2(String s) {

        int n=s.length();
        char[] c=s.toCharArray();
        int[] dp=new int[n];
        if(c[0]!='0') dp[0]=1;
        if(n==1) return 1;
        if(c[1]!='0'&&c[0]!='0')dp[1]+=dp[0];
        int t=(c[1]-'0')*10+c[0]-'0';
        if(10<=t&&t <=26)dp[1]+=1;
        for(int i=2;i<n;i++){
            if(c[i]!='0')dp[i]+=dp[i-1];
            int tt=(c[i-1]-'0')*10+c[i]-'0';
            if(10<=tt&&tt <=26)dp[i]+=dp[i-2];
        }
        return dp[n-1];
    }
    //优化
    public int numDecodings(String s) {

        int n=s.length();
        char[] c=s.toCharArray();
        int[] dp=new int[n+1];
        dp[0]=1;
        if(c[0]!='0') dp[1]=1;
        for(int i=2;i<=n;i++){
            if(c[i-1]!='0')dp[i]+=dp[i-1];
            int tt=(c[i-2]-'0')*10+c[i-1]-'0';
            if(10<=tt&&tt <=26)dp[i]+=dp[i-2];
        }
        return dp[n];
    }
}